|
Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Let P(α) be a property defined for all ordinals α. Suppose that whenever P(β) is true for all β < α, then P(α) is also true. Then transfinite induction tells us that P is true for all ordinals. Usually the proof is broken down into three cases: * Zero case: Prove that P(0) is true. * Successor case: Prove that for any successor ordinal α+1, P(α+1) follows from P(α) (and, if necessary, P(β) for all β < α). * Limit case: Prove that for any limit ordinal λ, P(λ) follows from (for all β < λ ). All three cases are identical except for the type of ordinal considered. They do not formally need to be considered separately, but in practice the proofs are typically so different as to require separate presentations. Zero is sometimes considered a limit ordinal and then may sometimes be treated in proofs in the same case as limit ordinals. ==Transfinite recursion== Transfinite recursion is similar to transfinite induction; however, instead of proving that something holds for all ordinal numbers, we construct a sequence of objects, one for each ordinal. As an example, a basis for a (possibly infinite-dimensional) vector space can be created by choosing a vector and for each ordinal α choosing a vector that is not in the span of the vectors . This process stops when no vector can be chosen. More formally, we can state the Transfinite Recursion Theorem as follows: * Transfinite Recursion Theorem (version 1). Given a class function〔A class function is a rule (specifically, a logical formula) assigning each element in the lefthand class to an element in the righthand class. It is not a function because its domain and codomain are not sets.〕 ''G'': ''V'' → ''V'' (where ''V'' is the class of all sets), there exists a unique transfinite sequence ''F'': Ord → ''V'' (where Ord is the class of all ordinals) such that :''F''(α) = ''G''(''F'' α) for all ordinals α, where denotes the restriction of ''Fs domain to ordinals < α. As in the case of induction, we may treat different types of ordinals separately: another formulation of transfinite recursion is the following: * Transfinite Recursion Theorem (version 2). Given a set ''g''1, and class functions ''G''2, ''G''3, there exists a unique function ''F'': Ord → ''V'' such that * ''F''(0) = ''g''1, * ''F''(α + 1) = ''G''2(''F''(α)), for all α ∈ Ord, * ''F''(λ) = ''G''3(''F'' λ), for all limit λ ≠ 0. Note that we require the domains of ''G''2, ''G''3 to be broad enough to make the above properties meaningful. The uniqueness of the sequence satisfying these properties can be proven using transfinite induction. More generally, one can define objects by transfinite recursion on any well-founded relation ''R''. (''R'' need not even be a set; it can be a proper class, provided it is a set-like relation; that is, for any ''x'', the collection of all ''y'' such that ''y R x'' must be a set.) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Transfinite induction」の詳細全文を読む スポンサード リンク
|